package lizhe.dummynode;


import java.io.UnsupportedEncodingException;
import java.util.Stack;

public class IsPalindrome {
    public static boolean isPalindrome(ListNode head) {


        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) {
            slow = slow.next;
        }
        ListNode reverse = reverse(slow);

        while (reverse != null) {
            if (reverse.val != head.val) {
                return false;
            }
            reverse = reverse.next;
            head = head.next;
        }

        return true;
    }

    public static boolean isPalindrome2(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode tmp = head;
        int length = 0;
        while (tmp != null) {
            stack.push(tmp.val);
            tmp = tmp.next;
            length++;
        }
        length >>= 1;

        for (int i = 0; i < length; i++) {
            if (stack.pop() != head.val) return false;
            head = head.next;
        }

        return true;
    }

    private static ListNode reverse(ListNode listNode) {
        ListNode pre = null;
        ListNode cur = listNode;


        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }

    public static void main(String[] args) throws CloneNotSupportedException {
        ListNode head = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        head.next = listNode2;
        ListNode listNode3 = new ListNode(3);
        listNode2.next = listNode3;
        ListNode listNode4 = new ListNode(4);
        listNode3.next = listNode4;
        ListNode listNode5 = new ListNode(5);
        listNode4.next = listNode5;

//        boolean palindrome = isPalindrome2(head);
//        System.out.println(palindrome);
        printListNode(head);
    }

    public static boolean isPalindrome3(ListNode head) {
        tmp = head;
        return check(head);
    }

    private static ListNode tmp;

    private static boolean check(ListNode head) {
        if (head == null) return true;

        boolean res = check(head.next) && tmp.val == head.val;
        tmp = tmp.next;
        return res;
    }

    private static void printListNode(ListNode head) {
        if (head == null) return;

        printListNode(head.next);
        System.out.println(head.val);
    }
}
